package fun.coding.dp;

import java.util.ArrayList;
import java.util.Arrays;

public class DPImpl implements DP {
	/**
	 * find the max contiguous sequence from a given array (with neg and pos int) that sum is the max.
	 * e.g., 0, -1, 2, -1, 3, -1, 0 (4 = 2, -1, 3)
	 * Dynamic programming's core idea is to use the results from previous steps. most likely store it somewhere in the tables. 
	 * S -> sum, A -> array
	 * S[0] = A[0]
	 * S[i] = max(S[i] + A[i+1], A[i+1]) where 1 < i < k 
	 * Reference
	 * http://tkramesh.wordpress.com/2011/03/
	 * There could be more than one, but we only want one.  
	 *
	 */
	public void maxSubSum(int[] A) {
		int s = A[0];
		int max = A[0];
		int maxIndexLast = 0;
		int maxIndexStart = 0;
		int t = 0;
		
		for(int i = 1; i < A.length; ++i) {
		    s = Math.max(s + A[i], A[i]);
		    /*
			if (s > 0) {
				s += A[i];
			} else {
				s = A[i];
				t = i;
			}
			*/
			
			if(s > max) {
				max = s;
				maxIndexLast = i;
				maxIndexStart = t;
			}
		}
		
		for(int i : A) {
			System.out.print(i + " ");
		}
		System.out.println();
		System.out.println(String.format("Max sum is %d", max));
		for(int i = maxIndexStart; i <= maxIndexLast; ++i) {
			System.out.print(A[i] + " ");
		}
		System.out.println();
		System.out.println("Done");

	}


	/**
	 * find the longest increasing sub sequence and print it out
	 * For example, [2, 9, 3, 4, 5, 7, 8, 9, 10, 1],
	 * would print out 7, 8, 9, 10.
	 * @param A
	 * @return the length of the longest sub string.
	 */
	public int longestSubSequence(int[] A) {
		int longestStartIndex = 1;
		int longestLength = 1;
		
		if(A.length == 0) {
			return 0;
		}
		if(A.length == 1) {
			return 1;
		}
		
		int length = 1;
		int index = 1;
		for(int i = 1; i < A.length - 1; ++i) {
			if((A[i+1] - A[i]) == 1) {
				length++;
			} else {
				index = i + 1;
				length = 1;
			}
			
			if(length > longestLength) {
				longestLength = length;
				longestStartIndex = index;
			}
		}
		
		System.out.println("longestStartIndex is " + longestStartIndex + " longestLength is " + longestLength);
		
		System.out.println("Longest sub seq is ");
		for(int i = 0; i < longestLength; ++i) {
			System.out.print(A[longestStartIndex + i] + "\t");
		}
		
		return longestLength;
	}

	/* Let's say you only have 1 sell and 1 buy option, find the max profit
	 * For example, {5, 9, 2, 13, 1, 8, 17} will return 16 {1, 17}
	 * @see interview.coding.dp.DP#maxStockProfit(int[])
	 */
	@Override
	public int maxStockProfit(int[] A) {
		int minPrice = A[0];
		int maxProfit = 0;
		int currentMin = A[0];
		
		for(int i = 1; i < A.length; i++) {
			
			if((A[i] - minPrice) > maxProfit) {
				maxProfit = A[i] - minPrice;
			}
			
			if((A[i] - currentMin) > maxProfit) {
				maxProfit = A[i] - currentMin;
				minPrice = currentMin;
			}
			
			if(A[i] < currentMin) {
				currentMin = A[i];
			}
		}
		
		return maxProfit;
	}

	/* the same as maxStockProfit, leetcode OJ. 
	 * Very simple and naive, just keep track of min and current maxProfit
	 * */
    @Override
    public int maxProfit(int[] prices) {
        if(prices == null || prices.length == 0)
            return 0;
        
        if(prices.length == 1) 
            return 0;
        
        int min = prices[0];
        int maxProfit = Integer.MIN_VALUE;
        
        for(int i = 0; i < prices.length; ++i) {
            if(prices[i] - min > maxProfit) {
                maxProfit = prices[i] - min;
            }
            if(prices[i] < min)
                min = prices[i];
            
        }
        
        return maxProfit;
    }

    /* Same as above, expect I could buy and sell multiple times. I can only buy after sell. 
     * 
     * The catch is to find all the increasing sequence, and add them all together. 
     * */
    @Override
    public int maxProfitMultiTrans(int[] prices) {
        if(prices == null || prices.length == 0 || prices.length == 1)
            return 0;
        
        int maxProfit = 0;
        int s = 0;
        for(int i = 1; i < prices.length; ++i) {
            if(prices[i] > prices[i - 1]) 
                continue;
 
                maxProfit += prices[i - 1] - prices[s];
                s = i;
        }
        
        maxProfit += prices[prices.length - 1] - prices[s];
        
        return maxProfit;
    }


	/*
	 * Leetcode selling stock III, here they say maximum is 2 times, here it can generalize to k times, and use I to O(kn)
	 * Wrong, this won't work for even [1,10,5,20] 
	 * http://www.mitbbs.com/article_t1/JobHunting/32251173_0_1.html
	 * 
	 * Very clever, divided into 2 parts, the part before you buy max on that day and after you buy max on that day.
	 * http://blog.unieagle.net/2012/12/05/leetcode%E9%A2%98%E7%9B%AE%EF%BC%9Abest-time-to-buy-and-sell-stock-iii%EF%BC%8C%E4%B8%80%E7%BB%B4%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/ 
	 * */
    @Override
    public int maxProfitKTimes(int[] prices) {
        if(prices==null || prices.length==0)
            return 0;
            
        int len=prices.length;
        int[] dp1=new int[len];
        int[] dp2=new int[len];
        int max=prices[len-1];
        int min=prices[0];
        
        for(int i=1;i<len;i++)
        {
            min=Math.min(min,prices[i]);
            dp1[i]=Math.max(dp1[i-1],prices[i]-min);
        }
        for(int i=len-2;i>=0;i--)
        {
            max=Math.max(max, prices[i]);
            dp2[i]=Math.max(dp2[i+1],max-prices[i]);
        }
        
        int ans=0;
        for(int i=0;i<len;i++)
            ans=Math.max(ans, dp1[i]+dp2[i]);
        return ans;
    }
    
	/*
	 * 
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
 The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
 It has to be adjacent nodes, not as simple as just find the minimum in each list. 
    -1
   2    3
 1   -1  -3 
 
 -1 + 3 -3 = -1
 The easy part it only requires the min sum, doesn't need to print out the path. 
 
 from the bottom up is the easiest way. 
	 */
	@Override
	public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
		if(triangle.size() == 0)
		    return 0;
		
		if(triangle.size() == 1)
		    return triangle.get(0).get(0);
		
		int[] a = new int[triangle.size()];
		ArrayList<Integer> temp = triangle.get(triangle.size() - 1);
		for(int i = 0; i < temp.size(); ++i) {
		    a[i] = temp.get(i);
		}
		
		for(int i = triangle.size() - 1; i >= 0; --i) {
		    if(i - 1 >= 0) {
		        calculateMin(a, triangle.get(i - 1));
		    }
		}
		
		return a[0];
	}
	
	private void calculateMin(int[] a, ArrayList<Integer> top) {
	    for(int i = 0; i < top.size(); ++i) {
	        a[i] = top.get(i) + Math.min(a[i], a[i + 1]);
	    }
	    /*
	    for(int i : a)
	        System.out.print(i + ",");
	    System.out.println();
	    */
	}

	
	/**
	 * This would be the most simple DP example ever
	 * 1) get a formular, 
	 * 2) cache the result. 
	 */
	private int[] fib = new int[100];
    @Override
    public int generateNthFibonacciNumber(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        
        if (fib[n] != 0) return fib[n];
        
        fib[n] = generateNthFibonacciNumber(n - 1) + generateNthFibonacciNumber(n - 2);
        return fib[n];
    }



	
}
